#include <iostream>
#include <vector>
using namespace std;

int SimapleArray[]={5,3,17,10,84,19,6,22,9};

class PrintInt
	{
	public:
		void operator()(int elem) const 
		{
			cout << elem<<' ';
		}
	};
//MAX-HEAPIFY by recursion
//i from one
void max_heapify_recursion(vector<int> &vec,int i)
{
	int l=2*i;
	int r=2*i+1;
	int largest;
	if(l<=vec.size()&&(vec[l-1]>vec[i-1]))
		largest=l;
	else {
		largest=i;
	}
	if((r<=vec.size())&&(vec[r-1]>vec[largest-1]))
		largest=r;
	if(largest!=i)
	{
		swap(vec[i-1],vec[largest-1]);
		max_heapify_recursion(vec,largest);
	}
	
}
void build_max_heap(vector<int> &vec)
{
	for(int i=vec.size()/2;i>0;i--)
	{
		max_heapify_recursion(vec,i);
	}
}
int main (int argc, char * const argv[]) {
    // insert code here...
	vector<int> A;
	int size=sizeof(SimapleArray)/sizeof(int);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
    cout << "Array before sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	build_max_heap(A);
	cout << "Array afert sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	
	cout<<endl;
	
    return 0;
}
